// https://www.lintcode.com/problem/longest-valid-parentheses/

public class Solution {
    /**
     * @param s: a string
     * @return: return a integer
     */
    public int longestValidParentheses(String s) {
        // write your code here
        int ret = 0, start = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            }
            else { // ')'
                if (stack.empty()) { // 没有匹配，试试下一个吧。。。
                    start  = i + 1;
                }
                else {
                    stack.pop();
                    if (stack.empty()) { // 空了，合并上次结果。
                        ret = Math.max(ret, i - start + 1);
                    }
                    else { // 更新ret
                        ret = Math.max(ret, i - stack.peek()); // peek查看栈顶元素
                    }
                }
            }
        }
        return ret;
    }
}